/*
https://leetcode.cn/problems/house-robber-iii/
*/
-----------------------------------------------------------------

#include <vector>
#include <queue>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    /**
     * 按层次遍历二叉树，并计算每一层的节点值总和。
     *
     * @param Root 二叉树的根节点
     * @return 每一层节点值总和的向量
     */
    vector<int> LevelSum(TreeNode* Root) {
        vector<int> Sum;
        queue<TreeNode*> Q;
        Q.push(Root);
        TreeNode *P, *Last = Root, *NewLast = nullptr;
        int Tmp = 0;

        while (!Q.empty()) {
            P = Q.front();
            Q.pop();
            Tmp += P->val;

            if (P->left) {
                Q.push(P->left);
                NewLast = P->left;
            }
            if (P->right) {
                Q.push(P->right);
                NewLast = P->right;
            }

            // 当前层结束
            if (P == Last) {
                Last = NewLast;
                Sum.push_back(Tmp);
                Tmp = 0;
            }
        }

        return Sum;
    }

    /**
     * 动态规划求解给定数值列表的最大不相邻元素和。
     *
     * @param V 数值列表
     * @return 最大不相邻元素和
     */
    int RobOfList(const vector<int>& V) {
        size_t Len = V.size();
        if (Len == 0) return 0; // 处理空列表的情况
        if (Len == 1) return V[0]; // 只有一个元素时直接返回

        vector<int> Dp(Len, 0);
        Dp[0] = V[0];
        Dp[1] = max(V[0], V[1]);

        for (size_t i = 2; i < Len; ++i) {
            Dp[i] = max(Dp[i - 1], Dp[i - 2] + V[i]);
        }

        return Dp[Len - 1];
    }

    /**
     * 计算在二叉树中选择节点以获得最大和，但不能选择相邻的节点。
     *
     * @param Root 二叉树的根节点
     * @return 最大和
     */
    int Rob(TreeNode* Root) {
        if (!Root) {
            return 0;
        }
        if (!Root->left && !Root->right) {
            return Root->val;
        }

        vector<int> LevelSums = LevelSum(Root); // 获取每层节点值总和
        return RobOfList(LevelSums); // 应用动态规划解决问题
    }
};

-----------------------------------------------------------------